package week5;

public class Sorting2 {
    /**
            * 用选择对指定的整数数组进行排序
     * 排序算法
     *
             * @param data 要排序的数组
     */
    public static <T extends Comparable<T>>
    void selectionSort(T[] data)
    {

        long startTime=System.nanoTime();
        int min;
        int count=0;
        T temp;
        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
            {
                if (data[scan].compareTo(data[min])<0)
                    min = scan;
                     count++;
            }

            swap(data, min, index);
        }
        long endTime=System.nanoTime(); //获取结束时间
        long Time=endTime-startTime;
        System.out.println("选择排序"+"比较次数:"+count+" "+"运行时间："+Time+"ns");
    }

    /**
     * 对数组中的元素进行交换。用于各种排序算法。.
     *
     * @param data  元素被交换的数组
     * @param index1 要交换的第一个元素的索引
     * @param index2 要交换的第二个元素的索引
     */
    private static <T extends Comparable<T>>
    void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /**
     * 使用插入对指定的对象数组进行排序
     * 排序算法.
     *
     * @param data 被搜索的数组
     */
    public static <T extends Comparable<T>>
    void insertionSort(T[] data)
    {
        long startTime=System.nanoTime();
        int count3=0;
        for (int index = 1; index < data.length; index++)
        {
            T key = data[index];
            int position = index;
            count3++;
            // 将更大的值转移到右边
            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                count3++;
                data[position] = data[position-1];
                position--;
            }
            data[position] = key;
        }
        long endTime=System.nanoTime(); //获取结束时间
        long Time=endTime-startTime;
        System.out.println("插入排序"+"比较次数:"+count3+" "+"运行时间："+Time+"ns");
    }

    /**
     * 使用冒泡排序对指定的数组进行排序
     * 算法
     *
     * @param data 被排序的数组
     */
    public static <T extends Comparable<T>>
    void bubbleSort(T[] data)
    {
        long startTime=System.nanoTime();
        int position, scan;
        int count=0;
        T temp;

        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                count++;
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
            }
        }
        long endTime=System.nanoTime(); //获取结束时间
        long Time=endTime-startTime;
        System.out.println("冒泡排序"+"比较次数:"+count+" "+"运行时间："+Time+"ns");

    }

    /**
     * 使用归并排序对指定的数组进行排序
     * 算法
     *
     * @param data 被排序的数组
     */
    public static <T extends Comparable<T>>
    void mergeSort(T[] data)
    {
        long startTime=System.nanoTime();
        mergeSort(data, 0, data.length - 1);
        long endTime=System.nanoTime(); //获取结束时间
        long Time=endTime-startTime;
        System.out.println("归并排序"+"比较次数:"+getcount()+" "+"运行时间："+Time+"ns");
         reset();
    }

    /**
     * 递归地对指定数组中的对象进行排序
     * 归并排序算法
     *
     * @param data 被排序的算法
     * @param min  第一个元素的索引
     * @param max  最后一个元素的索引
     */
    private static <T extends Comparable<T>>
    void mergeSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
        }

    /**
     * 合并指定数组的两个排序子数组。
     *
     * @param data 被排序的数组
     * @param first 第一个子数组的开始索引
     * @param mid 第一个子数组的结束索引
     * @param last 第二个子数组的结束索引
     */
    @SuppressWarnings("unchecked")

    private static <T extends Comparable<T>>
    void merge(T[] data, int first, int mid, int last)
    {
        T[] temp = (T[])(new Comparable[data.length]);

        int first1 = first, last1 = mid;  // 第一个子数组的端点
        int first2 = mid+1, last2 = last;  // 第二个子数组的端点
        int index = first1;  // 下一个在临时数组中打开的索引

        //将子数组中的元素复制到temp中知道子数组中的元素被用尽
        while (first1 <= last1 && first2 <= last2)
        {
             recordcount();
            if (data[first1].compareTo(data[first2]) < 0)
            {
                temp[index] = data[first1];
                first1++;

            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //  如果第一个子数组有元素，则保留第一个数组中保留剩余的元素
        while (first1 <= last1)
        {

            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  如果第二个子数组有元素，则保留第二个数组中保留剩余的元素
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  将合并后的数据复制到原始数组中
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }
     static int count1=0;
   public  static void recordcount()
   {
       count1++;
       }
   public static void reset()
   {
       count1=0;
   }
   public static int getcount(){
        return count1;
    }

    /**
     * 使用快速排序算法对指定的对象数组进行排序。
     *
     * @param data 被排序的数组
     */
    public static <T extends Comparable<T>>
    void quickSort(T[] data)
    { long startTime=System.nanoTime();
        quickSort(data, 0, data.length - 1);
        long endTime=System.nanoTime(); //获取结束时间
        long Time=endTime-startTime;
        System.out.println("快速排序"+"比较次数:"+getcount()+" "+"运行时间："+Time+"ns");
        reset();

    }

    /**
     * 用快速排序算法递归的对指定数组进行排序
     * @param data 被排序的数组
     * @param min  在范围内被排序的最小值索引
     * @param max  在范围内被排序的最大值索引
     */
    private static <T extends Comparable<T>>
    void quickSort(T[] data, int min, int max)
    {

        if (min < max)
        {
            // 创建分区
            int indexofpartition = partition(data, min, max);

            // 排序左分区（低一级分区）
            quickSort(data, min, indexofpartition - 1);

            // 排序右分区（高一级分区）
            quickSort(data, indexofpartition + 1, max);
        }

    }

    /**
     * 使用快速排序算法找到分区
     *
     * @param data 被排序的数组
     * @param min  范围内被排序的最小值索引
     * @param max  范围内被排序的最大值索引
     */

    private static <T extends Comparable<T>>
    int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        // 使用中间的数据作为分区元素
        partitionelement = data[middle];
        // 现在移动它出这个方式
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // 搜索大于分区元素的元素
            recordcount();
            while (left < right && data[left].compareTo(partitionelement) <= 0)
            {
                recordcount();
                left++;
                }
                // 搜索小于分区元素的元素
            while (data[right].compareTo(partitionelement) > 0)
            {
                recordcount();
                right--;
                }

            // 交换元素
            if (left < right)
                swap(data, left, right);
        }

        // 将分区元素移动到适合的位置
        swap(data, min, right);
        return right;
    }
}

